using System;
using System.Collections.Generic;
using System.Text;
using CoreCalc;
using C5;

namespace CoreCalc.SheetDefinedFunctions
{
  /// <summary>
  /// A graph representation of the dependencies between the function sheet 
  /// cell involved in a sheet-defined function.  Records the set 
  /// nodesPrecedents[fca] of cells directly referred by the formula in cell fca, as 
  /// well as the set nodesDependents[fca] of the cells directly referring to cell fca.
  /// </summary>

  public class DependencyGraph
  {
    /// <summary>
    /// Map from a cell to its dependents: the cells that directly depend on it.
    /// </summary>
    private readonly Dictionary<FullCellAddr, HashSet<FullCellAddr>> nodesDependents;

    /// <summary>
    /// Map from a cell to its precedents: the cells on which it directly depends.
    /// </summary>
    private readonly Dictionary<FullCellAddr, HashSet<FullCellAddr>> nodesPrecedents;

    public readonly FullCellAddr outputCell;
    public readonly FullCellAddr[] inputCells;
    public readonly HashSet<FullCellAddr> inputCellSet;
    // Maps a full cell address to the Formula or CGExpr at that address
    private readonly Fun<FullCellAddr, IDepend> getNode;

    public DependencyGraph(FullCellAddr outputCell, FullCellAddr[] inputCells, Fun<FullCellAddr,IDepend> getNode)
    {
      this.outputCell = outputCell;
      this.nodesDependents = new Dictionary<FullCellAddr, HashSet<FullCellAddr>>();
      this.nodesPrecedents = new Dictionary<FullCellAddr, HashSet<FullCellAddr>>();
      this.inputCells = inputCells;
      this.inputCellSet = new HashSet<FullCellAddr>();
      this.inputCellSet.AddAll(inputCells);
      this.getNode = getNode;
    }

    public HashSet<FullCellAddr> GetDependents(FullCellAddr fca)
    {
      return nodesDependents[fca];
    }

    /// <summary>
    /// Make "precedent" a precedent of "node", and 
    /// make "node" a dependent of "precedent".  
    /// If the required sets of precedents resp. dependents do not exist, 
    /// create them and associate them with "node" resp. "precedent".
    /// </summary>
    /// <exception cref="CyclicException">If a static cycle exists</exception>
    public bool AddPrecedentDependent(FullCellAddr precedent, FullCellAddr node)
    {
      HashSet<FullCellAddr> precedents;

      if (nodesPrecedents.TryGetValue(node, out precedents))
      {
        try
        {
          precedents.Add(precedent);
        }
        catch (ArgumentException) 
        {
          //Happens if the element already exists: there is a cycle
          throw new CyclicException("Static cycle involving cell " + precedent);
        }
      }
      else
      {
        precedents = new HashSet<FullCellAddr>();
        precedents.Add(precedent);
        nodesPrecedents.Add(node, precedents);
      }

      HashSet<FullCellAddr> kids;

      if (nodesDependents.TryGetValue(precedent, out kids))
      {
        try
        {
          kids.Add(node);
        }
        catch (ArgumentException)
        {
          //Happens if the element already exists: these is a cycle
          throw new CyclicException("Static cycle involving cell " + node);
        }
        return true;
      }
      else
      {
        kids = new HashSet<FullCellAddr>();
        kids.Add(node);
        nodesDependents.Add(precedent, kids);
        return false;
      }
    }

    /// <summary>
    /// Tests whether transitiveDependents contains any cell transitively dependent on node.
    /// </summary>
    /// <param name="node"></param>
    /// <param name="possibleDependents"></param>
    /// <returns></returns>

    public bool HasDependent(FullCellAddr node, C5.ICollection<FullCellAddr> transitiveDependents)
    {
      HashSet<FullCellAddr> visitedCells = new HashSet<FullCellAddr>();
      return HasDependentHelper(node, transitiveDependents, visitedCells);
    }

    private bool HasDependentHelper(FullCellAddr node, C5.ICollection<FullCellAddr> transitiveDependents,
        HashSet<FullCellAddr> visitedCells)
    {
      HashSet<FullCellAddr> dependents;
      if (nodesDependents.TryGetValue(node, out dependents))
      {
        foreach (FullCellAddr addr in transitiveDependents)
          if (dependents.Contains(addr))
            return true;
        foreach (FullCellAddr addr in dependents)
          if (visitedCells.Add(addr)) // returns true only first time
            if (HasDependentHelper(addr, transitiveDependents, visitedCells))
              return true;
      }
      return false;
    }

    /// <summary>
    /// Tests whether possiblePrecedents contains any cell that node 
    /// transitively depends on. 
    /// </summary>
    /// <param name="node"></param>
    /// <param name="transitivePrecedents"></param>
    /// <returns></returns>

    public bool HasPrecedent(FullCellAddr node, C5.ICollection<FullCellAddr> transitivePrecedents)
    {
      HashSet<FullCellAddr> visitedCells = new HashSet<FullCellAddr>();
      return HasPrecedentHelper(node, transitivePrecedents, visitedCells);
    }

    private bool HasPrecedentHelper(FullCellAddr node, C5.ICollection<FullCellAddr> transitivePrecedents, HashSet<FullCellAddr> visitedCells)
    {
      HashSet<FullCellAddr> precedents;
      if (nodesPrecedents.TryGetValue(node, out precedents))
      {
        foreach (FullCellAddr addr in transitivePrecedents)
          if (precedents.Contains(addr))
            return true;
        foreach (FullCellAddr addr in precedents)
          if (visitedCells.Add(addr))
            if (HasPrecedentHelper(addr, transitivePrecedents, visitedCells))
              return true;
      }
      return false;
    }

    internal bool TryGetValue(FullCellAddr node, out HashSet<FullCellAddr> kids)
    {
      return nodesPrecedents.TryGetValue(node, out kids);
    }

    /// <summary>
    /// Build the (two-way) dependency graph whose nodes are the 
    /// output cell and all cells (on the same function sheet) on 
    /// which it transitively depends.
    /// </summary>
    /// <exception cref="CyclicException"></exception>
    public void CollectPrecedents()
    {
      GetTransitivePrecedents(outputCell);
    }

    public C5.IList<FullCellAddr> GetAllNodes()
    {
      // The full set of precedent cells is the output cell plus all cells
      // on which something depends -- true, but a funny way to compute it.
      C5.IList<FullCellAddr> result = new ArrayList<FullCellAddr>();
      result.AddAll(nodesDependents.Keys);
      result.Add(outputCell);
      return result;
    }

    /// <summary>
    /// Find all transitive precedents, that is, cells 
    /// that this cell transitively depends on.
    /// The cell thisFca is within the function sheet being translated.  
    /// Cells outside the function sheet are not traced.
    /// </summary>
    /// <param name="thisFca"></param>
    /// <exception cref="CyclicException"></exception>
    private void GetTransitivePrecedents(FullCellAddr thisFca)
    {
      HashSet<FullCellAddr> precedents = new HashSet<FullCellAddr>();
      IDepend node = getNode(thisFca);      
      if (node != null)
        node.DependsOn(thisFca, delegate(FullCellAddr fca) { precedents.Add(fca); });

      // Now precedents is the set of cells directly referred from 
      // the Expr in cell thisFca; that is, that cell's direct precedents

      foreach (FullCellAddr addr in precedents)
        // Trace dependencies only from cells on this sheet, 
        // and don't trace precedents of input cells
        if (addr.sheet == thisFca.sheet) 
          if (!AddPrecedentDependent(addr, thisFca) && !inputCellSet.Contains(addr))
            GetTransitivePrecedents(addr);
    }
  }
}